{ "cells": [ { "cell_type": "markdown", "id": "baf262e9", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Information Theory" ] }, { "cell_type": "markdown", "id": "fbe2b798", "metadata": { "slideshow": { "slide_type": "-" }, "tags": [ "remove-cell" ] }, "source": [ "**CS1302 Introduction to Computer Programming**\n", "___" ] }, { "cell_type": "markdown", "id": "fac1857f", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "As mentioned in previous lectures, the following two lists `coin_flips` and `dice_rolls` simulate the random coin flips and rollings of a dice:" ] }, { "cell_type": "code", "execution_count": 1, "id": "59cc5118", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "a97ace8ad9849cd240a2783dfe1d06ed", "grade": false, "grade_id": "random", "locked": true, "schema_version": 3, "solution": false, "task": false }, "slideshow": { "slide_type": "-" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "coin flips: T T H H T H T H H T T T H T T H T T T T H T T T H H H T T T H T H T T H T H T T H H T H H T H T H T T H H H T T H T T T T T T T T H T H T H H H T T H H T T T T T T T H T H T T T T T T H T T T T H T H T T H T H H T H T H H T H T T T T H T T T H H T H H T H H H T T H H H H H T H H T H H T H H T T T H T T H T T H H T H H H H T T H H T H T H T H H H H T H H H T T T T H H T H H H H T H T T H H T H T H\n", "dice rolls: 4 1 3 6 2 4 5 4 5 5 1 1 4 3 3 4 1 4 2 5 6 1 6 2 1 4 6 4 3 1 2 1 6 1 6 5 5 1 2 1 5 6 2 3 3 6 2 1 4 4 6 1 1 3 4 1 3 2 6 5 6 6 3 1 2 3 1 1 1 2 6 3 5 3 3 5 1 6 6 5 6 4 6 6 4 6 4 3 5 2 2 4 5 3 1 2 2 3 3 3 3 6 1 3 5 1 1 3 2 2 5 3 3 4 5 2 3 1 4 6 2 1 3 2 5 6 1 3 4 3 3 4 1 1 5 4 4 3 3 1 4 1 6 4 4 1 3 3 6 6 2 2 6 5 4 6 1 1 1 2 6 2 1 4 1 1 4 5 5 3 4 4 5 6 6 2 4 1 3 2 3 5 2 4 2 3 1 1 6 1 5 4 6 2 1 4 4 3 2 6\n" ] } ], "source": [ "# Do NOT modify any variables defined here because some tests rely on them\n", "import random\n", "import math\n", "\n", "random.seed(0) # for reproducible results.\n", "num_trials = 200\n", "coin_flips = [\"H\" if random.random() <= 1 / 2 else \"T\" for i in range(num_trials)]\n", "dice_rolls = [random.randint(1, 6) for i in range(num_trials)]\n", "print(\"coin flips: \", *coin_flips)\n", "print(\"dice rolls: \", *dice_rolls)" ] }, { "cell_type": "markdown", "id": "639d7729", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**What is the difference of the two random processes? \n", "Can we say one process has more information content than the other?**" ] }, { "cell_type": "markdown", "id": "dbcf6dbc", "metadata": { "slideshow": { "slide_type": "-" } }, "source": [ "In this Lab, we will use dictionaries to store their distributions and then compute their information content using information theory, which was introduced by *Claude E. Shannon*. It has [numerous applications](https://www.khanacademy.org/computing/computer-science/informationtheory): \n", "- *compression* (to keep files small)\n", "- *communications* (to send data mobile phones), and \n", "- *machine learning* (to identify relevant features to learn from)." ] }, { "cell_type": "markdown", "id": "dedb7043", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Entropy" ] }, { "cell_type": "markdown", "id": "7b63f19f", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Mathematically, we denote a distribution as $\\mathbf{p}=[p_i]_{i\\in \\mathcal{S}}$, where \n", "- $\\mathcal{S}$ is the set of distinct outcomes, and\n", "- $p_i$ denotes the probability (chance) of seeing outcome $i$." ] }, { "cell_type": "markdown", "id": "f6898797", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The following code shown in the lecture uses a dictionary to store the distribution for a sequence efficiently without storing outcomes with zero counts:" ] }, { "cell_type": "code", "execution_count": 2, "id": "99a2c625", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "7b57cc639b55481c8c09e3f2640a6322", "grade": false, "grade_id": "dist", "locked": true, "schema_version": 3, "solution": false, "task": false }, "slideshow": { "slide_type": "-" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Distribution of coin flips: {'T': 0.5350000000000004, 'H': 0.4650000000000003}\n", "Distribution of dice rolls: {4: 0.17000000000000007, 1: 0.2150000000000001, 3: 0.18500000000000008, 6: 0.16500000000000006, 2: 0.14500000000000005, 5: 0.12000000000000004}\n" ] } ], "source": [ "# Do NOT modify any variables defined here because some tests rely on them\n", "def distribute(seq):\n", " \"\"\"Returns a dictionary where each value in a key-value pair is\n", " the probability of the associated key occuring in the sequence.\n", " \"\"\"\n", " p = {}\n", " for i in seq:\n", " p[i] = p.get(i, 0) + 1 / len(seq)\n", " return p\n", "\n", "\n", "# tests\n", "coin_flips_dist = distribute(coin_flips)\n", "dice_rolls_dist = distribute(dice_rolls)\n", "print(\"Distribution of coin flips:\", coin_flips_dist)\n", "print(\"Distribution of dice rolls:\", dice_rolls_dist)" ] }, { "cell_type": "markdown", "id": "2b00d196", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "For $\\mathbf{p}$ to be a valid distribution, the probabilities $p_i$'s have to sum to $1$, i.e.,\n", "\n", "$$\\sum_{i\\in \\mathcal{S}} p_i = 1, $$\n", "which can be verified as follows:" ] }, { "cell_type": "code", "execution_count": 3, "id": "b6bcc1da", "metadata": { "slideshow": { "slide_type": "-" } }, "outputs": [], "source": [ "assert math.isclose(sum(coin_flips_dist.values()), 1) and math.isclose(\n", " sum(dice_rolls_dist.values()), 1\n", ")" ] }, { "cell_type": "markdown", "id": "08c64668", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**How to measure the information content?**" ] }, { "cell_type": "code", "execution_count": 4, "id": "4a208caf", "metadata": { "slideshow": { "slide_type": "-" }, "tags": [ "hide-input" ] }, "outputs": [ { "data": { "text/html": [ "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "%%html\n", "" ] }, { "cell_type": "markdown", "id": "ab466816", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "````{prf:definition} Entropy\n", "\n", "In information theory, the information content of a distribution is measured by its [*entropy*](https://en.wikipedia.org/wiki/Entropy_(information_theory)) defined as:\n", "\n", "$$ \n", "\\begin{aligned} \n", "H(\\mathbf{p}) &:= \\sum_{i\\in \\mathcal{S}} p_i \\overbrace{\\log_2 \\tfrac{1}{p_i}}^{\\text{called surprise} } \\\\ \n", "&= - \\sum_{i\\in \\mathcal{S}} p_i \\log_2 p_i \\kern1em \\text{(bits)} \\end{aligned} \n", "$$\n", "\n", "with $p_i \\log_2 \\frac{1}{p_i} = 0$ if $p_i = 0$ because $\\lim_{x\\downarrow 0} x \\log_2 \\frac1x = 0$.\n", "\n", "````" ] }, { "cell_type": "markdown", "id": "d9cf0eef", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "For instance, if $\\mathbf{p}=(p_{H},p_{T})=(0.5,0.5)$, then\n", "\n", "$$\n", "\\begin{aligned} H(\\mathbf{p}) &= 0.5 \\log_2 \\frac{1}{0.5} + 0.5 \\log_2 \\frac{1}{0.5} \\\\ &= 0.5 + 0.5 = 1 \\text{ bit,}\\end{aligned} \n", "$$\n", "\n", "i.e., an outcome of a fair coin flip has one bit of information content, as expected." ] }, { "cell_type": "markdown", "id": "53b972b7", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "On the other hand, if $\\mathbf{p}=(p_{H},p_{T})=(1,0)$, then\n", "\n", "$$\n", "\\begin{aligned} H(\\mathbf{p}) &= 1 \\log_2 \\frac{1}{1} + 0 \\log_2 \\frac{1}{0} \\\\ &= 0 + 0 = 0 \\text{ bits,}\\end{aligned} \n", "$$\n", "\n", "i.e., an outcome of a biased coin flip that always comes up head has no information content, again as expected." ] }, { "cell_type": "markdown", "id": "adc28573", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**Exercise** Define a function `entropy` that\n", "- takes a distribution $\\mathbf{p}$ as its argument, and\n", "- returns the entropy $H(\\mathbf{p})$.\n", "\n", "Handle the case when $p_i=0$, e.g., using the short-circuit evaluation of logical `and`." ] }, { "cell_type": "code", "execution_count": 5, "id": "91caf954", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "86985a3479afc26fcc7159dfc27e3bf2", "grade": false, "grade_id": "entropy", "locked": false, "schema_version": 3, "solution": true, "task": false }, "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [], "source": [ "def entropy(dist):\n", " # YOUR CODE HERE\n", " raise NotImplementedError()" ] }, { "cell_type": "code", "execution_count": 6, "id": "d3938331", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "c1eed6deedf3bc6f5c779b373b29abd9", "grade": true, "grade_id": "test-entropy", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false }, "slideshow": { "slide_type": "-" }, "tags": [ "hide-input", "remove-output" ] }, "outputs": [ { "ename": "NotImplementedError", "evalue": "", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;31m# tests\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0;32massert\u001b[0m \u001b[0mmath\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0misclose\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mentropy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m{\u001b[0m\u001b[0;34m\"H\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"T\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 3\u001b[0m \u001b[0;32massert\u001b[0m \u001b[0mmath\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0misclose\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mentropy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m{\u001b[0m\u001b[0;34m\"H\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"T\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32massert\u001b[0m \u001b[0mmath\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0misclose\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mentropy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdict\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mfromkeys\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m7\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1\u001b[0m \u001b[0;34m/\u001b[0m \u001b[0;36m6\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmath\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlog2\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m6\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36mentropy\u001b[0;34m(dist)\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mentropy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdist\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0;31m# YOUR CODE HERE\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mNotImplementedError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m: " ] } ], "source": [ "# tests\n", "assert math.isclose(entropy({\"H\": 0.5, \"T\": 0.5}), 1)\n", "assert math.isclose(entropy({\"H\": 1, \"T\": 0}), 0)\n", "assert math.isclose(entropy(dict.fromkeys(range(1, 7), 1 / 6)), math.log2(6))" ] }, { "cell_type": "code", "execution_count": 7, "id": "7c6fc760", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "c491b1f6a16eb521a7933e3377e29207", "grade": true, "grade_id": "h_test-entropy", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false }, "tags": [ "remove-cell" ] }, "outputs": [], "source": [ "# hidden tests" ] }, { "cell_type": "markdown", "id": "2792e44d", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Uniform distribution maximizes entropy" ] }, { "cell_type": "markdown", "id": "98269690", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Intuitively,\n", "- for large enough numbers of fair coin flips, we should have $\\mathcal{S}=\\{H,T\\}$ and $p_H=p_T=0.5$, i.e., equal chance for head and tail.\n", "- for large enough numbers of fair dice rolls, we should have $p_i=\\frac16$ for all $i\\in \\mathcal{S}=\\{1,2,3,4,5,6\\}$." ] }, { "cell_type": "code", "execution_count": 8, "id": "af6b36d2", "metadata": { "slideshow": { "slide_type": "-" } }, "outputs": [ { "data": { "application/vnd.jupyter.widget-view+json": { "model_id": "a08482a6943d4f9bbd1441c21b1df5a3", "version_major": 2, "version_minor": 0 }, "text/plain": [ "interactive(children=(IntSlider(value=1, continuous_update=False, description='n:', max=200, min=1), Output())…" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "import matplotlib.pyplot as plt\n", "\n", "\n", "def plot_distribution(seq):\n", " dist = distribute(seq)\n", " plt.stem(\n", " dist.keys(), # set-like view of the keys\n", " dist.values(), # view of the values\n", " use_line_collection=True,\n", " )\n", " plt.xlabel(\"Outcomes\")\n", " plt.title(\"Distribution\")\n", " plt.ylim(0, 1)\n", "\n", "\n", "import ipywidgets as widgets\n", "\n", "n_widget = widgets.IntSlider(\n", " value=1,\n", " min=1,\n", " max=num_trials,\n", " step=1,\n", " description=\"n:\",\n", " continuous_update=False,\n", ")\n", "\n", "widgets.interactive(lambda n: plot_distribution(coin_flips[:n]), n=n_widget)" ] }, { "cell_type": "code", "execution_count": 9, "id": "f47423fb", "metadata": { "slideshow": { "slide_type": "-" } }, "outputs": [ { "data": { "application/vnd.jupyter.widget-view+json": { "model_id": "c24a3456f53e453d86b6cf16a1b93f6e", "version_major": 2, "version_minor": 0 }, "text/plain": [ "interactive(children=(IntSlider(value=1, continuous_update=False, description='n:', max=200, min=1), Output())…" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "widgets.interactive(lambda n: plot_distribution(dice_rolls[:n]), n=n_widget)" ] }, { "cell_type": "markdown", "id": "ec27f25c", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "````{prf:definition} Uniform\n", "\n", "A distribution is called a *uniform distribution* if all its distinct outcomes have the same probability of occuring, i.e.,\n", "\n", "$$ p_i = \\frac{1}{|\\mathcal{S}|}\\kern1em \\text{for all }i\\in \\mathcal{S}, $$\n", "\n", "where $|\\mathcal{S}|$ is the mathematical notation to denote the size of the set $\\mathcal{S}$.\n", "\n", "````" ] }, { "cell_type": "markdown", "id": "8b59b510", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**Exercise** Define a function `uniform` that\n", "- takes a sequence of possibly duplicate outcomes, and\n", "- returns a uniform distribution on the distinct outcomes." ] }, { "cell_type": "code", "execution_count": 10, "id": "f7a65871", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "0aa5198d49ee7ae1dab4533dfc8b9b05", "grade": false, "grade_id": "uniform", "locked": false, "schema_version": 3, "solution": true, "task": false }, "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [], "source": [ "def uniform(outcomes):\n", " \"\"\"Returns the uniform distribution (dict) over distinct items in outcomes.\"\"\"\n", " # YOUR CODE HERE\n", " raise NotImplementedError()" ] }, { "cell_type": "code", "execution_count": 11, "id": "b04bbe66", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "34ff6d478ccd4d04a8684fb5d5c5a2ed", "grade": true, "grade_id": "test-uniform", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false }, "slideshow": { "slide_type": "-" }, "tags": [ "remove-output", "hide-input" ] }, "outputs": [ { "ename": "NotImplementedError", "evalue": "", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;31m# tests\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0;32massert\u001b[0m \u001b[0muniform\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"HT\"\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;34m\"H\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"T\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 3\u001b[0m \u001b[0;32massert\u001b[0m \u001b[0muniform\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"HTH\"\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;34m\"H\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"T\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0mfair_dice_dist\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0muniform\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m7\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m assert all(\n", "\u001b[0;32m\u001b[0m in \u001b[0;36muniform\u001b[0;34m(outcomes)\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0;34m\"\"\"Returns the uniform distribution (dict) over distinct items in outcomes.\"\"\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 3\u001b[0m \u001b[0;31m# YOUR CODE HERE\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mNotImplementedError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m: " ] } ], "source": [ "# tests\n", "assert uniform(\"HT\") == {\"H\": 0.5, \"T\": 0.5}\n", "assert uniform(\"HTH\") == {\"H\": 0.5, \"T\": 0.5}\n", "fair_dice_dist = uniform(range(1, 7))\n", "assert all(\n", " math.isclose(fair_dice_dist[k], v)\n", " for k, v in {\n", " 1: 0.16666666666666666,\n", " 2: 0.16666666666666666,\n", " 3: 0.16666666666666666,\n", " 4: 0.16666666666666666,\n", " 5: 0.16666666666666666,\n", " 6: 0.16666666666666666,\n", " }.items()\n", ")" ] }, { "cell_type": "code", "execution_count": 12, "id": "fbdaa41b", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "ce7d7550340006f67b4f4ff8f26f5b06", "grade": true, "grade_id": "h_test-uniform", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false }, "tags": [ "remove-cell" ] }, "outputs": [], "source": [ "# hidden tests" ] }, { "cell_type": "markdown", "id": "8bdea33d", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**What is the entropy for uniform distributions?**" ] }, { "cell_type": "markdown", "id": "b5853622", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "By definition,\n", "\n", "$$ \\begin{aligned} H(\\mathbf{p}) &:= \\sum_{i\\in \\mathcal{S}} p_i \\log_2 \\tfrac{1}{p_i} \\\\ &= \\sum_{i\\in \\mathcal{S}} \\frac{1}{|\\mathcal{S}|} \\log_2 |\\mathcal{S}| = \\log_2 |\\mathcal{S}| \\kern1em \\text{(bits)} \\end{aligned} $$\n", "\n", "This reduces to the formula you learned in Lecture 1 and Lab 1 regarding the number of bits required to represent a set. This is the maximum possible entropy for a given finite set of possible outcomes." ] }, { "cell_type": "markdown", "id": "20738f09", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "You can use this result to test whether you have implemented both `entropy` and `uniform` correctly:" ] }, { "cell_type": "code", "execution_count": 13, "id": "08b35d6e", "metadata": { "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [ { "ename": "NotImplementedError", "evalue": "", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m assert all(\n\u001b[0m\u001b[1;32m 2\u001b[0m \u001b[0mmath\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0misclose\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mentropy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0muniform\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmath\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlog2\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mn\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m100\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 3\u001b[0m )\n", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m(.0)\u001b[0m\n\u001b[1;32m 1\u001b[0m assert all(\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0mmath\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0misclose\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mentropy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0muniform\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmath\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlog2\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mn\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m100\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 3\u001b[0m )\n", "\u001b[0;32m\u001b[0m in \u001b[0;36muniform\u001b[0;34m(outcomes)\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0;34m\"\"\"Returns the uniform distribution (dict) over distinct items in outcomes.\"\"\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 3\u001b[0m \u001b[0;31m# YOUR CODE HERE\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mNotImplementedError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m: " ] } ], "source": [ "assert all(\n", " math.isclose(entropy(uniform(range(n))), math.log2(n)) for n in range(1, 100)\n", ")" ] }, { "cell_type": "markdown", "id": "26b088f1", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Joint distribution and its entropy" ] }, { "cell_type": "markdown", "id": "e9737259", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "If we duplicate a sequence of outcomes, the total information content should remain unchanged, NOT doubled, because the duplicate contain the same information as the original. We will verify this fact by creating a [joint distribution](https://en.wikipedia.org/wiki/Joint_probability_distribution) \n", "\n", "$$\\mathbf{p}=[p_{ij}]_{i\\in \\mathcal{S},j\\in \\mathcal{T}}$$ \n", "- where $\\mathcal{S}$ and $\\mathcal{T}$ are sets of outcomes; and\n", "- $p_{ij}$ is the chance we see outcomes $i$ and $j$ simultaneously. \n", "\n", "The subscript $ij$ in $p_{ij}$ denotes a tuple $(i,j)$, NOT the multiplication $i\\times j$. We also have\n", "\n", "$$\\sum_{i\\in \\mathcal{S}} \\sum_{j\\in \\mathcal{T}} p_{ij} = 1.$$" ] }, { "cell_type": "markdown", "id": "7189a13e", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**Exercise** Define a function `jointly_distribute` that \n", "- takes two sequences `seq1` and `seq2` of outcomes with the same length, and\n", "- returns the joint distribution represented as a dictionary where each key-value pair has the key being a tuple `(i,j)` associated with the probability $p_{ij}$ of seeing `(i,j)` in `zip(seq1,seq2)`." ] }, { "cell_type": "code", "execution_count": 14, "id": "797a4dbc", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "125cfad4c0fe2e721c43fe470e14285d", "grade": false, "grade_id": "jointly_distribute", "locked": false, "schema_version": 3, "solution": true, "task": false }, "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [], "source": [ "def jointly_distribute(seq1, seq2):\n", " \"\"\"Returns the joint distribution of the tuple (i,j) of outcomes from zip(seq1,seq2).\"\"\"\n", " # YOUR CODE HERE\n", " raise NotImplementedError()" ] }, { "cell_type": "code", "execution_count": 15, "id": "edb0e467", "metadata": { "code_folding": [], "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "bfcce3ccfb4e20724ac509135fb23acf", "grade": true, "grade_id": "test-jointly_distribute", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false }, "slideshow": { "slide_type": "-" }, "tags": [ "remove-output", "hide-input" ] }, "outputs": [ { "ename": "NotImplementedError", "evalue": "", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;31m# tests\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0;32massert\u001b[0m \u001b[0mjointly_distribute\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"HT\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"HT\"\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"H\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"H\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;34m\"T\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"T\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 3\u001b[0m assert jointly_distribute(\"HHTT\", \"HTHT\") == {\n\u001b[1;32m 4\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;34m\"H\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"H\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.25\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;34m\"H\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"T\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.25\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36mjointly_distribute\u001b[0;34m(seq1, seq2)\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0;34m\"\"\"Returns the joint distribution of the tuple (i,j) of outcomes from zip(seq1,seq2).\"\"\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 3\u001b[0m \u001b[0;31m# YOUR CODE HERE\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mNotImplementedError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m: " ] } ], "source": [ "# tests\n", "assert jointly_distribute(\"HT\", \"HT\") == {(\"H\", \"H\"): 0.5, (\"T\", \"T\"): 0.5}\n", "assert jointly_distribute(\"HHTT\", \"HTHT\") == {\n", " (\"H\", \"H\"): 0.25,\n", " (\"H\", \"T\"): 0.25,\n", " (\"T\", \"H\"): 0.25,\n", " (\"T\", \"T\"): 0.25,\n", "}\n", "coin_flips_duplicate_dist = {\n", " (\"T\", \"T\"): 0.5350000000000004,\n", " (\"H\", \"H\"): 0.4650000000000003,\n", "}\n", "coin_flips_duplicate_ans = jointly_distribute(coin_flips, coin_flips)\n", "assert all(\n", " math.isclose(coin_flips_duplicate_ans[i], pi)\n", " for i, pi in coin_flips_duplicate_dist.items()\n", ")" ] }, { "cell_type": "code", "execution_count": 16, "id": "6ca16041", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "ef951eec230e55c0e722bfbef2bc0701", "grade": true, "grade_id": "h_test-jointly_distribute", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false }, "tags": [ "remove-cell" ] }, "outputs": [], "source": [ "# hidden tests" ] }, { "cell_type": "markdown", "id": "c96f6164", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "If you have implemented `entropy` and `jointly_distribute` correctly, you can verify that duplicating a sequence will give the same entropy." ] }, { "cell_type": "code", "execution_count": 17, "id": "b24f9157", "metadata": { "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [ { "ename": "NotImplementedError", "evalue": "", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n\u001b[1;32m 1\u001b[0m assert math.isclose(\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0mentropy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mjointly_distribute\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcoin_flips\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcoin_flips\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mentropy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdistribute\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcoin_flips\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 3\u001b[0m )\n\u001b[1;32m 4\u001b[0m assert math.isclose(\n\u001b[1;32m 5\u001b[0m \u001b[0mentropy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mjointly_distribute\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdice_rolls\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdice_rolls\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mentropy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdistribute\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdice_rolls\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36mjointly_distribute\u001b[0;34m(seq1, seq2)\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0;34m\"\"\"Returns the joint distribution of the tuple (i,j) of outcomes from zip(seq1,seq2).\"\"\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 3\u001b[0m \u001b[0;31m# YOUR CODE HERE\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mNotImplementedError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m: " ] } ], "source": [ "assert math.isclose(\n", " entropy(jointly_distribute(coin_flips, coin_flips)), entropy(distribute(coin_flips))\n", ")\n", "assert math.isclose(\n", " entropy(jointly_distribute(dice_rolls, dice_rolls)), entropy(distribute(dice_rolls))\n", ")" ] }, { "cell_type": "markdown", "id": "176b9dfc", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "However, for two sequences generated independently, the joint entropy is roughly the sum of the individual entropies." ] }, { "cell_type": "code", "execution_count": 18, "id": "687375e1", "metadata": { "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [ { "ename": "NotImplementedError", "evalue": "", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mcoin_flips_entropy\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mentropy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdistribute\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcoin_flips\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 2\u001b[0m \u001b[0mdice_rolls_entropy\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mentropy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdistribute\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdice_rolls\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 3\u001b[0m \u001b[0mcf_dr_entropy\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mentropy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mjointly_distribute\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcoin_flips\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdice_rolls\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 4\u001b[0m print(\n\u001b[1;32m 5\u001b[0m f\"\"\"Entropy of coin flip: {coin_flips_entropy}\n", "\u001b[0;32m\u001b[0m in \u001b[0;36mentropy\u001b[0;34m(dist)\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mentropy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdist\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0;31m# YOUR CODE HERE\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mNotImplementedError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m: " ] } ], "source": [ "coin_flips_entropy = entropy(distribute(coin_flips))\n", "dice_rolls_entropy = entropy(distribute(dice_rolls))\n", "cf_dr_entropy = entropy(jointly_distribute(coin_flips, dice_rolls))\n", "print(\n", " f\"\"\"Entropy of coin flip: {coin_flips_entropy}\n", "Entropy of dice roll: {dice_rolls_entropy}\n", "Sum of the above entropies: {coin_flips_entropy + dice_rolls_entropy}\n", "Joint entropy: {cf_dr_entropy}\"\"\"\n", ")" ] }, { "cell_type": "markdown", "id": "372fd4ff", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "## Conditional distribution and entropy" ] }, { "cell_type": "markdown", "id": "bc4860cb", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Mathematically, we denote a [conditional distribution](https://en.wikipedia.org/wiki/Conditional_probability_distribution) as $\\mathbf{q}:=[q_{j|i}]_{i\\in \\mathcal{S}, j\\in \\mathcal{T}}$, where \n", "- $\\mathcal{S}$ and $\\mathcal{T}$ are two sets of distinct outcomes, and\n", "- $q_{j|i}$ denotes the probability (chance) of seeing outcome $j$ given the condition that outcome $i$ is observed.\n", "\n", "For $\\mathbf{q}$ to be a valid distribution, the probabilities $q_{j|i}$'s have to sum to $1$ for every $i$, i.e.,\n", "\n", "$$\\sum_{j\\in \\mathcal{T}} q_{j|i} = 1 \\kern1em \\text{for all }i\\in \\mathcal{S} $$" ] }, { "cell_type": "markdown", "id": "e0e11dc0", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "For example, suppose we want to compute the distribution of coin flips given dice rolls, then the following assign `q_H_1` and `q_T_1` to the values $q_{H|1}$ and $q_{T|1}$ respectively:" ] }, { "cell_type": "code", "execution_count": 19, "id": "f6b9142c", "metadata": { "slideshow": { "slide_type": "-" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Coin flips given dice roll is 1: ['T', 'T', 'T', 'T', 'T', 'H', 'T', 'T', 'T', 'H', 'T', 'T', 'H', 'H', 'T', 'T', 'T', 'H', 'T', 'T', 'T', 'H', 'H', 'T', 'H', 'H', 'T', 'H', 'H', 'H', 'H', 'H', 'H', 'T', 'H', 'T', 'H', 'H', 'H', 'H', 'H', 'H', 'H']\n", "Distribution of coin flip given dice roll is 1: { \"H\": 0.5348837209302325, \"T\": 0.46511627906976744}\n" ] } ], "source": [ "coin_flips_1 = [j for i, j in zip(dice_rolls, coin_flips) if i == 1]\n", "q_H_1 = coin_flips_1.count(\"H\") / len(coin_flips_1)\n", "q_T_1 = coin_flips_1.count(\"T\") / len(coin_flips_1)\n", "print(\"Coin flips given dice roll is 1:\", coin_flips_1)\n", "print(\n", " 'Distribution of coin flip given dice roll is 1: {{ \"H\": {}, \"T\": {}}}'.format(\n", " q_H_1, q_T_1\n", " )\n", ")\n", "assert math.isclose(q_H_1 + q_T_1, 1)" ] }, { "cell_type": "markdown", "id": "4562e12b", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Note that `q_H_1 + q_T_1` is 1 as expected. Similarly, we can assign `q_H_2` and `q_T_2` to the values $q_{H|2}$ and $q_{T|2}$ respectively." ] }, { "cell_type": "code", "execution_count": 20, "id": "62773623", "metadata": { "slideshow": { "slide_type": "-" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Coin flips given dice roll is 2: ['T', 'T', 'T', 'H', 'T', 'T', 'H', 'T', 'T', 'H', 'T', 'T', 'T', 'T', 'T', 'H', 'T', 'T', 'T', 'T', 'T', 'H', 'H', 'T', 'T', 'T', 'H', 'T', 'T']\n", "Distribution of coin flip given dice roll is 2: { \"H\": 0.2413793103448276, \"T\": 0.7586206896551724}\n" ] } ], "source": [ "coin_flips_2 = [j for i, j in zip(dice_rolls, coin_flips) if i == 2]\n", "q_H_2 = coin_flips_2.count(\"H\") / len(coin_flips_2)\n", "q_T_2 = coin_flips_2.count(\"T\") / len(coin_flips_2)\n", "print(\"Coin flips given dice roll is 2:\", coin_flips_2)\n", "print(\n", " 'Distribution of coin flip given dice roll is 2: {{ \"H\": {}, \"T\": {}}}'.format(\n", " q_H_2, q_T_2\n", " )\n", ")\n", "assert math.isclose(q_H_2 + q_T_2, 1)" ] }, { "cell_type": "markdown", "id": "93680e41", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Finally, we want to store the conditional distribution as a nested dictionary so that `q[i]` points to the distribution \n", "\n", "$$[q_{j|i}]_{j\\in \\mathcal{T}} \\kern1em \\text{for }i\\in \\mathcal{S}.$$" ] }, { "cell_type": "code", "execution_count": 21, "id": "46cc8522", "metadata": { "slideshow": { "slide_type": "-" } }, "outputs": [ { "data": { "text/plain": [ "{1: {'H': 0.5348837209302325, 'T': 0.46511627906976744},\n", " 2: {'H': 0.2413793103448276, 'T': 0.7586206896551724}}" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "q = {}\n", "q[1] = dict(zip(\"HT\", (q_H_1, q_T_1)))\n", "q[2] = dict(zip(\"HT\", (q_H_2, q_T_2)))\n", "q" ] }, { "cell_type": "markdown", "id": "a81c51d3", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Of course, the above dictionary is missing the entries for other possible outcomes of the dice rolls." ] }, { "cell_type": "markdown", "id": "3875f74c", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**Exercise** Define a function `conditionally_distribute` that\n", "- takes two sequences `seq1` and `seq2` of outcomes of the same length, and\n", "- returns the conditional distribution of `seq2` given `seq1` in the form of a nested dictionary efficiently without storing the unobserved outcomes.\n", "\n", "In the above example, `seq1` is `dice_rolls` while `seq2` is `coin_flips`.\n", "\n", "*Hint:* For an efficient implementation without traversing the input sequences too many times, consider using the following solution template and the `setdefault` method.\n", "```Python\n", "def conditionally_distribute(seq1, seq2):\n", " q, count = {}, {} # NOT q = count = {}\n", " for i in seq1:\n", " count[i] = count.get(i, 0) + 1\n", " for i, j in zip(seq1, seq2):\n", " q[i][j] = ____________________________________________________\n", " return q\n", "```" ] }, { "cell_type": "code", "execution_count": 22, "id": "a2889360", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "8594de52bcc1c6d3ba64624a68e9fa5d", "grade": false, "grade_id": "conditionally_distribute", "locked": false, "schema_version": 3, "solution": true, "task": false }, "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [], "source": [ "def conditionally_distribute(seq1, seq2):\n", " \"\"\"Returns the conditional distribution q of seq2 given seq1 such that\n", " q[i] is a dictionary for observed outcome i in seq1 and\n", " q[i][j] is the probability of observing j in seq2 given the\n", " corresponding outcome in seq1 is i.\"\"\"\n", " # YOUR CODE HERE\n", " raise NotImplementedError()" ] }, { "cell_type": "code", "execution_count": 23, "id": "67fc5a57", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "c93ceb34d906b9dcefb3ebe4b1a71a97", "grade": true, "grade_id": "test-conditionally_distribute", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false }, "slideshow": { "slide_type": "-" }, "tags": [ "hide-input", "remove-output" ] }, "outputs": [ { "ename": "NotImplementedError", "evalue": "", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n\u001b[1;32m 8\u001b[0m \u001b[0;36m5\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;34m\"T\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5416666666666666\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"H\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.4583333333333333\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 9\u001b[0m }\n\u001b[0;32m---> 10\u001b[0;31m \u001b[0mcf_given_dr_ans\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mconditionally_distribute\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdice_rolls\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcoin_flips\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 11\u001b[0m assert all(\n\u001b[1;32m 12\u001b[0m \u001b[0mmath\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0misclose\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcf_given_dr_ans\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mj\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mv\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36mconditionally_distribute\u001b[0;34m(seq1, seq2)\u001b[0m\n\u001b[1;32m 5\u001b[0m corresponding outcome in seq1 is i.\"\"\"\n\u001b[1;32m 6\u001b[0m \u001b[0;31m# YOUR CODE HERE\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 7\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mNotImplementedError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m: " ] } ], "source": [ "# tests\n", "cf_given_dr_dist = {\n", " 4: {\"T\": 0.5588235294117647, \"H\": 0.4411764705882353},\n", " 1: {\"T\": 0.46511627906976744, \"H\": 0.5348837209302325},\n", " 3: {\"H\": 0.5135135135135135, \"T\": 0.4864864864864865},\n", " 6: {\"H\": 0.5454545454545454, \"T\": 0.45454545454545453},\n", " 2: {\"T\": 0.7586206896551724, \"H\": 0.2413793103448276},\n", " 5: {\"T\": 0.5416666666666666, \"H\": 0.4583333333333333},\n", "}\n", "cf_given_dr_ans = conditionally_distribute(dice_rolls, coin_flips)\n", "assert all(\n", " math.isclose(cf_given_dr_ans[i][j], v)\n", " for i, d in cf_given_dr_dist.items()\n", " for j, v in d.items()\n", ")" ] }, { "cell_type": "code", "execution_count": 24, "id": "a9d531c8", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "f56be0a7301a0e0983aea9c79f84d7cb", "grade": true, "grade_id": "h_test-conditionally_distribute", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false }, "tags": [ "remove-cell" ] }, "outputs": [], "source": [ "# hidden tests" ] }, { "cell_type": "markdown", "id": "8e23efac", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "````{prf:definition} Conditional entropy\n", "\n", "The [*conditional entropy*](https://en.wikipedia.org/wiki/Conditional_entropy) is defined for a conditional distribution $\\mathbf{q}=[q_{j|i}]_{i\\in \\mathcal{S},j\\in\\mathcal{T}}$ and a distribution $\\mathbf{p}=[p_i]_{i\\in \\mathcal{S}}$ as follows:\n", "\n", "$$ H(\\mathbf{q}|\\mathbf{p}) = \\sum_{i\\in \\mathcal{S}} p_i \\sum_{j\\in \\mathcal{T}} q_{j|i} \\log_2 \\frac{1}{q_{j|i}}, $$\n", "where, by convention, \n", "- the summand of the outer sum is 0 if $p_i=0$ (regardless of the values of $q_{j|i}$), and\n", "- the summand of the inner sum is 0 if $q_{j|i}=0$.\n", "\n", "````" ] }, { "cell_type": "markdown", "id": "6f0eb86b", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**Exercise** Define a function `conditional_entropy` that\n", "- takes \n", " - a distribution p as its first argument,\n", " - a conditional distribution q as its second argument, and\n", "- returns the conditional entropy $H(\\mathbf{q}|\\mathbf{p})$.\n", "\n", "Handle the cases when $p_i=0$ and $q_{j|i}=0$ as well." ] }, { "cell_type": "code", "execution_count": 25, "id": "9314266a", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "c6b8cc3d81731e285ecd4c206f7b72cb", "grade": false, "grade_id": "conditional_entropy", "locked": false, "schema_version": 3, "solution": true, "task": false }, "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [ { "ename": "NotImplementedError", "evalue": "", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;31m# YOUR CODE HERE\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mNotImplementedError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m: " ] } ], "source": [ "# YOUR CODE HERE\n", "raise NotImplementedError()" ] }, { "cell_type": "code", "execution_count": 26, "id": "53260aaa", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "2d1ae55ab94aa96569d2670cdb572dca", "grade": true, "grade_id": "test-conditional_entropy", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false }, "slideshow": { "slide_type": "-" }, "tags": [ "remove-output", "hide-input" ] }, "outputs": [ { "ename": "NameError", "evalue": "name 'conditional_entropy' is not defined", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mNameError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n\u001b[1;32m 9\u001b[0m }\n\u001b[1;32m 10\u001b[0m assert (\n\u001b[0;32m---> 11\u001b[0;31m conditional_entropy(\n\u001b[0m\u001b[1;32m 12\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;34m\"H\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"T\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;34m\"H\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;34m\"H\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"T\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"T\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;34m\"H\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"T\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 13\u001b[0m )\n", "\u001b[0;31mNameError\u001b[0m: name 'conditional_entropy' is not defined" ] } ], "source": [ "# tests\n", "cf_given_dr_dist = {\n", " 4: {\"T\": 0.5588235294117647, \"H\": 0.4411764705882353},\n", " 1: {\"T\": 0.46511627906976744, \"H\": 0.5348837209302325},\n", " 3: {\"H\": 0.5135135135135135, \"T\": 0.4864864864864865},\n", " 6: {\"H\": 0.5454545454545454, \"T\": 0.45454545454545453},\n", " 2: {\"T\": 0.7586206896551724, \"H\": 0.2413793103448276},\n", " 5: {\"T\": 0.5416666666666666, \"H\": 0.4583333333333333},\n", "}\n", "assert (\n", " conditional_entropy(\n", " {\"H\": 0.5, \"T\": 0.5}, {\"H\": {\"H\": 0.5, \"T\": 0.5}, \"T\": {\"H\": 0.5, \"T\": 0.5}}\n", " )\n", " == 1\n", ")\n", "assert (\n", " conditional_entropy(\n", " {\"H\": 0, \"T\": 1}, {\"H\": {\"H\": 0.5, \"T\": 0.5}, \"T\": {\"H\": 0.5, \"T\": 0.5}}\n", " )\n", " == 1\n", ")\n", "assert (\n", " conditional_entropy(\n", " {\"H\": 0.5, \"T\": 0.5}, {\"H\": {\"H\": 1, \"T\": 0}, \"T\": {\"H\": 0, \"T\": 1}}\n", " )\n", " == 0\n", ")\n", "assert (\n", " conditional_entropy(\n", " {\"H\": 0.5, \"T\": 0.5}, {\"H\": {\"H\": 1, \"T\": 0}, \"T\": {\"H\": 0.5, \"T\": 0.5}}\n", " )\n", " == 0.5\n", ")\n", "assert math.isclose(\n", " conditional_entropy(dice_rolls_dist, cf_given_dr_dist), 0.9664712793722372\n", ")" ] }, { "cell_type": "code", "execution_count": 27, "id": "7ea5453e", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "b22277acec7715d45059add1de697ab6", "grade": true, "grade_id": "h_test-conditional_entropy", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false }, "tags": [ "remove-cell" ] }, "outputs": [], "source": [ "# hidden tests" ] }, { "cell_type": "markdown", "id": "22398a28", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The joint probability $p_{ij}$ over $i\\in \\mathcal{S}$ and $j\\in \\mathcal{T}$ can be calculated as follows\n", "\n", "$$p_{ij} = p_{i} q_{j|i}$$\n", "where $p_i$ is the probability of $i$ and $q_{j|i}$ is the conditional probability of $j$ given $i$." ] }, { "cell_type": "markdown", "id": "b65d9aa4", "metadata": {}, "source": [ "**Exercise** Define a function `joint_distribution` that\n", "- takes the distribution $p$ and conditional distribution $q$ as arguments, and\n", "- returns their joint distribution." ] }, { "cell_type": "code", "execution_count": 28, "id": "bd2a0635", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "9926072602132dabef0a83e32a868b52", "grade": false, "grade_id": "joint_distribution", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "def joint_distribution(p, q):\n", " # YOUR CODE HERE\n", " raise NotImplementedError()" ] }, { "cell_type": "code", "execution_count": 29, "id": "ac2e3681", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "269d98d3de67bf0c28111dba49be4e0f", "grade": true, "grade_id": "test-joint_distribution", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false }, "tags": [ "remove-output", "hide-input" ] }, "outputs": [ { "ename": "NotImplementedError", "evalue": "", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;31m# tests\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m assert joint_distribution(\n\u001b[0m\u001b[1;32m 3\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;34m\"H\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"T\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;34m\"H\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;34m\"H\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"T\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"T\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;34m\"H\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"T\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 4\u001b[0m ) == {(\"H\", \"H\"): 0.25, (\"H\", \"T\"): 0.25, (\"T\", \"H\"): 0.25, (\"T\", \"T\"): 0.25}\n\u001b[1;32m 5\u001b[0m assert joint_distribution(\n", "\u001b[0;32m\u001b[0m in \u001b[0;36mjoint_distribution\u001b[0;34m(p, q)\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mjoint_distribution\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mp\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mq\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0;31m# YOUR CODE HERE\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mNotImplementedError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m: " ] } ], "source": [ "# tests\n", "assert joint_distribution(\n", " {\"H\": 0.5, \"T\": 0.5}, {\"H\": {\"H\": 0.5, \"T\": 0.5}, \"T\": {\"H\": 0.5, \"T\": 0.5}}\n", ") == {(\"H\", \"H\"): 0.25, (\"H\", \"T\"): 0.25, (\"T\", \"H\"): 0.25, (\"T\", \"T\"): 0.25}\n", "assert joint_distribution(\n", " {\"H\": 0, \"T\": 1}, {\"H\": {\"H\": 0.5, \"T\": 0.5}, \"T\": {\"H\": 0.5, \"T\": 0.5}}\n", ") == {(\"H\", \"H\"): 0.0, (\"H\", \"T\"): 0.0, (\"T\", \"H\"): 0.5, (\"T\", \"T\"): 0.5}\n", "assert joint_distribution(\n", " {\"H\": 0.5, \"T\": 0.5}, {\"H\": {\"H\": 1, \"T\": 0}, \"T\": {\"H\": 0, \"T\": 1}}\n", ") == {(\"H\", \"H\"): 0.5, (\"H\", \"T\"): 0.0, (\"T\", \"H\"): 0.0, (\"T\", \"T\"): 0.5}, {\n", " \"H\": 0.5,\n", " \"T\": 0.5,\n", "}" ] }, { "cell_type": "code", "execution_count": 30, "id": "e0c8cd77", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "5011b0b04d86a03ab5cf47508e4477bd", "grade": true, "grade_id": "h_test-joint_distribution", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false }, "tags": [ "remove-cell" ] }, "outputs": [], "source": [ "# hidden tests" ] }, { "cell_type": "markdown", "id": "0cdf551b", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Finally, a fundamental information identity relating the joint and conditional entropies is the [*chain rule*](https://en.wikipedia.org/wiki/Conditional_entropy#Chain_rule):" ] }, { "cell_type": "markdown", "id": "840fd0ff", "metadata": {}, "source": [ "````{prf:proposition} \n", "\n", "The joint entropy is equal to\n", "\n", "$$ H(\\mathbf{p}) + H(\\mathbf{q}|\\mathbf{p})$$\n", "\n", "for any distribution $\\mathbf{p}$ over outcome $i\\in \\mathcal{S}$ and conditional distribution $\\mathbf{q}$ over outcome $j\\in \\mathcal{T}$ given outcome $i \\in \\mathcal{S}$. \n", "\n", "````" ] }, { "cell_type": "markdown", "id": "eea2094b", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "If you have implemented `jointly_distribute`, `conditionally_distribute`, `entropy`, and `conditional_entropy` correctly, we can verify the identity as follows." ] }, { "cell_type": "code", "execution_count": 31, "id": "c2047528", "metadata": { "slideshow": { "slide_type": "-" } }, "outputs": [], "source": [ "def validate_chain_rule(seq1, seq2):\n", " p = distribute(seq1)\n", " q = conditionally_distribute(seq1, seq2)\n", " pq = jointly_distribute(seq1, seq2)\n", " H_pq = entropy(pq)\n", " H_p = entropy(p)\n", " H_q_p = conditional_entropy(p, q)\n", " print(\n", " f\"\"\"Entropy of seq1: {H_p}\n", "Conditional entropy of seq2 given seq1: {H_q_p}\n", "Sum of the above entropies: {H_p + H_q_p}\n", "Joint entropy: {H_pq}\"\"\"\n", " )\n", " assert math.isclose(H_pq, H_p + H_q_p)" ] }, { "cell_type": "code", "execution_count": 32, "id": "e9ed7902", "metadata": { "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [ { "ename": "NotImplementedError", "evalue": "", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mvalidate_chain_rule\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcoin_flips\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcoin_flips\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;32m\u001b[0m in \u001b[0;36mvalidate_chain_rule\u001b[0;34m(seq1, seq2)\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mvalidate_chain_rule\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mseq1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mseq2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0mp\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mdistribute\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mseq1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0mq\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mconditionally_distribute\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mseq1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mseq2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 4\u001b[0m \u001b[0mpq\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mjointly_distribute\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mseq1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mseq2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0mH_pq\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mentropy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpq\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36mconditionally_distribute\u001b[0;34m(seq1, seq2)\u001b[0m\n\u001b[1;32m 5\u001b[0m corresponding outcome in seq1 is i.\"\"\"\n\u001b[1;32m 6\u001b[0m \u001b[0;31m# YOUR CODE HERE\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 7\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mNotImplementedError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m: " ] } ], "source": [ "validate_chain_rule(coin_flips, coin_flips)" ] }, { "cell_type": "code", "execution_count": 33, "id": "2ea65c5c", "metadata": { "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [ { "ename": "NotImplementedError", "evalue": "", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mvalidate_chain_rule\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdice_rolls\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcoin_flips\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;32m\u001b[0m in \u001b[0;36mvalidate_chain_rule\u001b[0;34m(seq1, seq2)\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mvalidate_chain_rule\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mseq1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mseq2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0mp\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mdistribute\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mseq1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0mq\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mconditionally_distribute\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mseq1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mseq2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 4\u001b[0m \u001b[0mpq\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mjointly_distribute\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mseq1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mseq2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0mH_pq\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mentropy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpq\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36mconditionally_distribute\u001b[0;34m(seq1, seq2)\u001b[0m\n\u001b[1;32m 5\u001b[0m corresponding outcome in seq1 is i.\"\"\"\n\u001b[1;32m 6\u001b[0m \u001b[0;31m# YOUR CODE HERE\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 7\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mNotImplementedError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;31mNotImplementedError\u001b[0m: " ] } ], "source": [ "validate_chain_rule(dice_rolls, coin_flips)" ] } ], "metadata": { "jupytext": { "text_representation": { "extension": ".md", "format_name": "myst", "format_version": 0.13, "jupytext_version": "1.10.3" } }, "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.8" }, "source_map": [ 14, 18, 23, 27, 55, 60, 67, 71, 77, 81, 115, 122, 132, 136, 146, 162, 172, 182, 190, 211, 235, 254, 258, 264, 298, 306, 318, 324, 346, 381, 400, 404, 412, 416, 427, 431, 446, 452, 474, 512, 531, 535, 549, 553, 570, 574, 584, 588, 605, 609, 626, 632, 643, 647, 666, 691, 726, 745, 758, 768, 788, 844, 863, 870, 876, 894, 925, 944, 948, 960, 964, 985, 994 ], "widgets": { "application/vnd.jupyter.widget-state+json": { "state": { "1434d7e92e194185a561f59ff3d31ac5": { "model_module": "@jupyter-widgets/base", "model_module_version": "1.2.0", "model_name": "LayoutModel", "state": { "_model_module": "@jupyter-widgets/base", "_model_module_version": "1.2.0", "_model_name": "LayoutModel", "_view_count": null, "_view_module": "@jupyter-widgets/base", "_view_module_version": "1.2.0", "_view_name": "LayoutView", "align_content": null, "align_items": null, "align_self": null, "border": null, "bottom": null, "display": null, "flex": null, "flex_flow": null, "grid_area": null, "grid_auto_columns": null, "grid_auto_flow": null, "grid_auto_rows": null, "grid_column": null, "grid_gap": null, "grid_row": null, "grid_template_areas": null, "grid_template_columns": null, "grid_template_rows": null, "height": null, "justify_content": null, "justify_items": null, "left": null, "margin": null, "max_height": null, "max_width": null, "min_height": null, "min_width": null, "object_fit": null, "object_position": null, "order": null, "overflow": null, "overflow_x": null, "overflow_y": null, "padding": null, "right": null, "top": null, "visibility": null, "width": null } }, "16d235d5152e45d49928294e6418e24c": { "model_module": "@jupyter-widgets/base", "model_module_version": "1.2.0", "model_name": "LayoutModel", "state": { "_model_module": "@jupyter-widgets/base", "_model_module_version": "1.2.0", "_model_name": "LayoutModel", "_view_count": null, "_view_module": "@jupyter-widgets/base", "_view_module_version": "1.2.0", "_view_name": "LayoutView", "align_content": null, "align_items": null, "align_self": null, "border": null, "bottom": null, "display": null, "flex": null, "flex_flow": null, "grid_area": null, "grid_auto_columns": null, "grid_auto_flow": null, "grid_auto_rows": null, "grid_column": null, "grid_gap": null, "grid_row": null, "grid_template_areas": null, "grid_template_columns": null, "grid_template_rows": null, "height": null, "justify_content": null, "justify_items": null, "left": null, "margin": null, "max_height": null, "max_width": null, "min_height": null, "min_width": null, "object_fit": null, "object_position": null, "order": null, "overflow": null, "overflow_x": null, "overflow_y": null, "padding": null, "right": null, "top": null, "visibility": null, "width": null } }, "42dfa5cef9dd4789989839863ebc0b32": { "model_module": "@jupyter-widgets/base", "model_module_version": "1.2.0", "model_name": "LayoutModel", "state": { "_model_module": "@jupyter-widgets/base", "_model_module_version": "1.2.0", "_model_name": "LayoutModel", "_view_count": null, "_view_module": "@jupyter-widgets/base", "_view_module_version": "1.2.0", "_view_name": "LayoutView", "align_content": null, "align_items": null, "align_self": null, "border": null, "bottom": null, "display": null, "flex": null, "flex_flow": null, "grid_area": null, "grid_auto_columns": null, "grid_auto_flow": null, "grid_auto_rows": null, "grid_column": null, "grid_gap": null, "grid_row": null, "grid_template_areas": null, "grid_template_columns": null, "grid_template_rows": null, "height": null, "justify_content": null, "justify_items": null, "left": null, "margin": null, "max_height": null, "max_width": null, "min_height": null, "min_width": null, "object_fit": null, "object_position": null, "order": null, "overflow": null, "overflow_x": null, "overflow_y": null, "padding": null, "right": null, "top": null, "visibility": null, "width": null } }, "69f2585328134adaa51dc59ae5305b88": { "model_module": "@jupyter-widgets/base", "model_module_version": "1.2.0", "model_name": "LayoutModel", "state": { "_model_module": "@jupyter-widgets/base", "_model_module_version": "1.2.0", "_model_name": "LayoutModel", "_view_count": null, "_view_module": "@jupyter-widgets/base", "_view_module_version": "1.2.0", "_view_name": "LayoutView", "align_content": null, "align_items": null, "align_self": null, "border": null, "bottom": null, "display": null, "flex": null, "flex_flow": null, "grid_area": null, "grid_auto_columns": null, "grid_auto_flow": null, "grid_auto_rows": null, "grid_column": null, "grid_gap": null, "grid_row": null, "grid_template_areas": null, "grid_template_columns": null, "grid_template_rows": null, "height": null, "justify_content": null, "justify_items": null, "left": null, "margin": null, "max_height": null, "max_width": null, "min_height": null, "min_width": null, "object_fit": null, "object_position": null, "order": null, "overflow": null, "overflow_x": null, "overflow_y": null, "padding": null, "right": null, "top": null, "visibility": null, "width": null } }, "6c7c58be118e4f0da3539e089bcac733": { "model_module": "@jupyter-widgets/output", "model_module_version": "1.0.0", "model_name": "OutputModel", "state": { "_dom_classes": [], "_model_module": "@jupyter-widgets/output", "_model_module_version": "1.0.0", "_model_name": "OutputModel", "_view_count": null, "_view_module": "@jupyter-widgets/output", "_view_module_version": "1.0.0", "_view_name": "OutputView", "layout": "IPY_MODEL_69f2585328134adaa51dc59ae5305b88", "msg_id": "", "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAEWCAYAAAB2X2wCAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/Z1A+gAAAACXBIWXMAAAsTAAALEwEAmpwYAAAQkklEQVR4nO3dfbBcdX3H8ffHGxAQBZXU6k1ArAGMVVBj1KGOKFYSHwrajoIogjIpo2ir1pIqWPtgpVqdlgHMZGiaQjtgtYwEGqUV67OMBCoPwcGmQcMlFhOpKKjFhG//2MUuN3vv7oUNyf35fs1kcs85vz37JUPeOTnZ3ZuqQpI0+z1iVw8gSRoNgy5JjTDoktQIgy5JjTDoktQIgy5JjTDomlWSrEhy1ojOdWCSu5OMdbe/kOTUUZy7e77PJHnTqM4nDTJnVw8g9UryHeAJwDZgO3AzcCGwsqruq6rTZnCeU6vqc1OtqapNwL4Pdebu830AeGpVvaHn/EtHcW5pWF6ha3f0qqp6NHAQcDZwBvC3o3yCJF7MqDkGXbutqrqrqtYArwPelOTXk6xO8ucASQ5IckWSHya5M8mXkzwiyUXAgcDl3Vsqf5jkyUkqyVuSbAI+37OvN+6/luQbSe5KclmSx3Wf66gkE73zJflOkpcmWQK8F3hd9/mu7x7/xS2c7lxnJvluku8nuTDJft1j98/xpiSbkmxN8r6d+6urFhl07faq6hvABPDCSYfe3d0/l85tmvd2ltcbgU10rvT3raoP9zzmRcDTgGOmeLqTgDcDT6Jz2+ecIeb7LPAXwCe6z3d4n2Und3+8GHgKnVs9505a8xvAocDRwPuTPG3Qc0u9DLpmi83A4ybt+znwROCgqvp5VX25Bn840Qeq6p6q+ukUxy+qqpuq6h7gLOC19/+j6UN0IvCxqtpYVXcDfwQcP+lvB39SVT+tquuB64F+fzBIUzLomi3GgTsn7fsIsAH41yQbkywf4jy3zeD4d4E9gAOGnnJqT+qer/fcc+j8zeJ+/93z9U8Y0T/Y6peHQdduL8lz6QT9K737q+rHVfXuqnoK8CrgXUmOvv/wFKcbdAU/v+frA+n8LWArcA+wT89MY3Ru9Qx73s10/pG399zbgDsGPE4amkHXbivJY5K8ErgE+IequnHS8VcmeWqSAD+i8zLH7d3Dd9C5Vz1Tb0iyMMk+wJ8Cn6qq7cC3gb2SvCLJHsCZwCN7HncH8OQkU/2euhh4Z5KDk+zL/99z3/YgZpT6MujaHV2e5Md0bn+8D/gYcEqfdQuAzwF3A18Hzq+qL3SPfQg4s/sKmD+YwXNfBKymc/tjL+Ad0HnFDfBW4ALgdjpX7L2vevlk9+cfJLmuz3lXdc/9JeBW4GfA22cwlzRQ/AYXktQGr9AlqREDg55kVfeNEDdNcTxJzkmyIckNSZ49+jElSYMMc4W+GlgyzfGldO5lLgCWAR9/6GNJkmZqYNCr6kvs+PrfXscCF1bH1cD+SZ44qgElScMZxQcUjfPAN2NMdPd9b/LCJMvoXMXzqEc96jmHHXbYCJ5eGo0bb79rymPPGN/vYZxEmtq11167tarm9js2iqCnz76+L52pqpXASoBFixbVunXrRvD00mgcefbnuf2HO34iwPj+e/PV5S/ZBRNJO0ry3amOjeJVLhM88N118+i8K06aVd5zzKHsvccDP7Zl7z3GeM8xh+6iiaSZGUXQ1wAndV/t8nzgrqra4XaLtLs77lnjfOg1z2DPsc5vi/H99+ZDr3kGxz1rfBdPJg1n4C2XJBcDRwEHdD8P+o/pfGARVbUCWAu8nM6HJP2E/u/ok2aF4541zsXf2ATAJ373Bbt4GmlmBga9qk4YcLyAt41sIknSg+I7RSWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEUMFPcmSJLck2ZBkeZ/j+yW5PMn1SdYnOWX0o0qSpjMw6EnGgPOApcBC4IQkCyctextwc1UdDhwFfDTJniOeVZI0jWGu0BcDG6pqY1XdC1wCHDtpTQGPThJgX+BOYNtIJ5UkTWuYoI8Dt/VsT3T39ToXeBqwGbgR+L2qum/yiZIsS7IuybotW7Y8yJElSf0ME/T02VeTto8Bvgk8CTgCODfJY3Z4UNXKqlpUVYvmzp07w1ElSdMZJugTwPye7Xl0rsR7nQJcWh0bgFuBw0YzoiRpGMME/RpgQZKDu//QeTywZtKaTcDRAEmeABwKbBzloJKk6c0ZtKCqtiU5HbgSGANWVdX6JKd1j68A/gxYneRGOrdozqiqrTtxbknSJAODDlBVa4G1k/at6Pl6M/Cy0Y4mSZoJ3ykqSY0w6JLUCIMuSY0w6JLUCIMuSY0w6JLUCIMuSY0w6JLUCIMuSY0w6JLUCIMuSY0w6JLUCIMuSY0w6JLUCIMuSY0w6JLUCIMuSY0w6JLUCIMuSY0w6JLUCIMuSY0w6JLUCIMuSY0w6JLUCIMuSY0w6JLUCIMuSY0w6JLUCIMuSY0w6JLUCIMuSY0w6JLUCIMuSY0w6JLUiKGCnmRJkluSbEiyfIo1RyX5ZpL1Sb442jElSYPMGbQgyRhwHvCbwARwTZI1VXVzz5r9gfOBJVW1Kcmv7KR5JUlTGOYKfTGwoao2VtW9wCXAsZPWvB64tKo2AVTV90c7piRpkGGCPg7c1rM90d3X6xDgsUm+kOTaJCf1O1GSZUnWJVm3ZcuWBzexJKmvYYKePvtq0vYc4DnAK4BjgLOSHLLDg6pWVtWiqlo0d+7cGQ8rSZrawHvodK7I5/dszwM291mztaruAe5J8iXgcODbI5lSkjTQMFfo1wALkhycZE/geGDNpDWXAS9MMifJPsDzgG+NdlRJ0nQGXqFX1bYkpwNXAmPAqqpan+S07vEVVfWtJJ8FbgDuAy6oqpt25uCSpAca5pYLVbUWWDtp34pJ2x8BPjK60SRJM+E7RSWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEQZdkhph0CWpEUMFPcmSJLck2ZBk+TTrnptke5LfGd2IkqRhDAx6kjHgPGApsBA4IcnCKdb9JXDlqIeUJA02zBX6YmBDVW2sqnuBS4Bj+6x7O/DPwPdHOJ8kaUjDBH0cuK1ne6K77xeSjAOvBlZMd6Iky5KsS7Juy5YtM51VkjSNYYKePvtq0vZfA2dU1fbpTlRVK6tqUVUtmjt37pAjSpKGMWeINRPA/J7tecDmSWsWAZckATgAeHmSbVX16VEMKUkabJigXwMsSHIwcDtwPPD63gVVdfD9XydZDVxhzCXp4TUw6FW1LcnpdF69Mgasqqr1SU7rHp/2vrkk6eExzBU6VbUWWDtpX9+QV9XJD30sSdJM+U5RSWqEQZekRhh0SWqEQZekRhh0SWqEQZekRhh0SWqEQZekRhh0SWqEQZekRhh0SWqEQZekRhh0SWqEQZekRhh0SWqEQZekRhh0SWqEQZekRhh0SWqEQZekRhh0SWqEQZekRhh0SWqEQZekRhh0SWqEQZekRhh0SWqEQZekRhh0SWqEQZekRhh0SWqEQZekRhh0SWqEQZekRgwV9CRLktySZEOS5X2On5jkhu6PryU5fPSjSpKmMzDoScaA84ClwELghCQLJy27FXhRVT0T+DNg5agHlSRNb5gr9MXAhqraWFX3ApcAx/YuqKqvVdX/dDevBuaNdkxJ0iDDBH0cuK1ne6K7bypvAT7T70CSZUnWJVm3ZcuW4aeUJA00TNDTZ1/1XZi8mE7Qz+h3vKpWVtWiqlo0d+7c4aeUJA00Z4g1E8D8nu15wObJi5I8E7gAWFpVPxjNeJKkYQ1zhX4NsCDJwUn2BI4H1vQuSHIgcCnwxqr69ujHlCQNMvAKvaq2JTkduBIYA1ZV1fokp3WPrwDeDzweOD8JwLaqWrTzxpYkTTbMLReqai2wdtK+FT1fnwqcOtrRJEkz4TtFJakRBl2SGmHQJakRBl2SGmHQJakRBl2SGmHQJakRBl2SGmHQJakRBl2SGmHQJakRBl2SGmHQJakRBl2SGmHQJakRBl2SGmHQJakRBl2SGmHQJakRBl2SGmHQJakRBl2SGmHQJakRBl2SGmHQJakRBl2SGmHQJakRBl2SGmHQJakRBl2SGmHQJakRBl2SGmHQJakRBl2SGmHQJakRQwU9yZIktyTZkGR5n+NJck73+A1Jnj36USVJ0xkY9CRjwHnAUmAhcEKShZOWLQUWdH8sAz4+4jklSQMMc4W+GNhQVRur6l7gEuDYSWuOBS6sjquB/ZM8ccSzSpKmMWeINePAbT3bE8DzhlgzDnyvd1GSZXSu4AHuTnLLjKaVHj4H/NNpbN3VQ0h9HDTVgWGCnj776kGsoapWAiuHeE5pl0qyrqoW7eo5pJkY5pbLBDC/Z3sesPlBrJEk7UTDBP0aYEGSg5PsCRwPrJm0Zg1wUvfVLs8H7qqq700+kSRp5xl4y6WqtiU5HbgSGANWVdX6JKd1j68A1gIvBzYAPwFO2XkjSw8Lbw1q1knVDre6JUmzkO8UlaRGGHRJasQwL1uUfikkeTxwVXfzV4HtwJbu9uLuG+uk3Zb30KU+knwAuLuq/mpXzyINy1suktQIgy5JjTDoktQIgy5JjTDoktQIgy5JjfBli5LUCK/QJakRBl2SGmHQJakRBl2SGmHQJakRBl2zUpJ5SS5L8p9J/ivJ33S/ReJ0j3nvwzWftCsYdM06SQJcCny6qhYAhwD7Ah8c8FCDrqYZdM1GLwF+VlV/B1BV24F3Am9O8tYk596/MMkVSY5Kcjawd5JvJvnH7rGTktyQ5PokF3X3HZTkqu7+q5Ic2N2/OsnHk/x7ko1JXpRkVZJvJVnd83wvS/L1JNcl+WSSfbv7z05yc/e8fiSvdgq/wYVmo6cD1/buqKofJdnEFP9PV9XyJKdX1REASZ4OvA84sqq2Jnlcd+m5wIVV9fdJ3gycAxzXPfZYOn+Y/BZwOXAkcCpwTZIjgAngTOClVXVPkjOAd3X/gHk1cFhVVZL9R/BrIO3AoGs2CtDvLc5T7e/nJcCnqmorQFXd2d3/AuA13a8vAj7c85jLu0G+Ebijqm4ESLIeeDIwD1gIfLVzV4g9ga8DPwJ+BlyQ5F+AK4acUZoRg67ZaD3w2707kjwGmA/cxQNvJe41xTmGjX/vmv/t/nxfz9f3b8+h8y3r/q2qTtjhyZLFwNHA8cDpdP5AkUbKe+iaja4C9klyEkCSMeCjwGpgI3BEkkckmQ8s7nncz5Ps0XOO13a/jyg9t1y+Rie6ACcCX5nBXFcDRyZ5avec+yQ5pHsffb+qWgv8PnDEDM4pDc0rdM063dserwbOT3IWnQuTtXRexXIvcCtwI3ATcF3PQ1cCNyS5rqpOTPJB4ItJtgP/AZwMvANYleQ9dL5B9CkzmGtLkpOBi5M8srv7TODHwGVJ9qLzN4N3Prj/cml6ftqiJDXCWy6S1AiDLkmNMOiS1AiDLkmNMOiS1AiDLkmNMOiS1Ij/A8uy6apbwh+eAAAAAElFTkSuQmCC\n", "text/plain": "
" }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ] } }, "a08482a6943d4f9bbd1441c21b1df5a3": { "model_module": "@jupyter-widgets/controls", "model_module_version": "1.5.0", "model_name": "VBoxModel", "state": { "_dom_classes": [ "widget-interact" ], "_model_module": "@jupyter-widgets/controls", "_model_module_version": "1.5.0", "_model_name": "VBoxModel", "_view_count": null, "_view_module": "@jupyter-widgets/controls", "_view_module_version": "1.5.0", "_view_name": "VBoxView", "box_style": "", "children": [ "IPY_MODEL_c90aaa6d9d2843f8b426ad65a5442410", "IPY_MODEL_6c7c58be118e4f0da3539e089bcac733" ], "layout": "IPY_MODEL_1434d7e92e194185a561f59ff3d31ac5" } }, "a6ba747e0c9c4628aa3cf885881d4e57": { "model_module": "@jupyter-widgets/output", "model_module_version": "1.0.0", "model_name": "OutputModel", "state": { "_dom_classes": [], "_model_module": "@jupyter-widgets/output", "_model_module_version": "1.0.0", "_model_name": "OutputModel", "_view_count": null, "_view_module": "@jupyter-widgets/output", "_view_module_version": "1.0.0", "_view_name": "OutputView", "layout": "IPY_MODEL_e5ec282970c141eea017482cb19e10fd", "msg_id": "", "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAEWCAYAAAB2X2wCAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/Z1A+gAAAACXBIWXMAAAsTAAALEwEAmpwYAAAUaklEQVR4nO3df7SdVX3n8ffHBMovBZTU0QQUKwqxCtpIbZ2OqJ0S1BZ1ZrVQWhRlGFbFtlotjKK14zjSOu3quECzsihDoVPpj8EKTJRO6VhtESEoEMHBSQNCwJEgFQVrMfCdP54ncnJy7r3nJufm3Gzfr7Xuynn23uc5Xzb3fu5z9jln31QVkqQ93xOmXYAkaTIMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjo2qMkWZPkPRM612FJHkqypD/+dJLTJ3Hu/nyfTPKGSZ1PmsvSaRcgDUpyJ/BUYCvwKHAbcAmwtqoeq6oz53Ge06vqr2caU1V3AQfsas39470PeHZV/dLA+U+YxLmlcXmFrsXoZ6vqicAzgPOAs4E/nOQDJPFiRs0x0LVoVdWDVXUF8AvAG5L8aJKLk/wngCSHJLkqyTeTPJDks0mekORS4DDgyn5J5TeTPDNJJXlzkruAvxloGwz3H0lyfZIHk3wiyZP7xzouyebB+pLcmeSnk6wG3gX8Qv94N/f931/C6es6N8lXk9yX5JIkB/Z92+p4Q5K7ktyf5N0LO7tqkYGuRa+qrgc2Az811PUbffsyumWad3XD65eBu+iu9A+oqt8duM/LgKOA42d4uFOBNwFPp1v2+fAY9X0K+M/An/aPd/SIYW/sv14OPItuqef8oTH/Engu8ErgvUmOmuuxpUEGuvYU9wJPHmr7HvA04BlV9b2q+mzNvTnR+6rq4ar6pxn6L62qL1XVw8B7gJ/f9qLpLjoF+P2q2lRVDwH/AThp6NnBb1fVP1XVzcDNwKhfDNKMDHTtKZYDDwy1fQjYCPxVkk1JzhnjPHfPo/+rwF7AIWNXObOn9+cbPPdSumcW2/y/gdvfYUIv2OoHh4GuRS/Ji+kC/e8G26vq21X1G1X1LOBngbcneeW27hlON9cV/KEDtw+jexZwP/AwsN9ATUvolnrGPe+9dC/yDp57K/D1Oe4njc1A16KV5ElJXgNcBvxxVW0Y6n9NkmcnCfAturc5Ptp3f51urXq+finJyiT7Af8R+IuqehT4CrBPklcn2Qs4F/ihgft9HXhmkpl+pj4GvC3J4UkO4PE19607UaM0koGuxejKJN+mW/54N/D7wGkjxh0B/DXwEPA54CNV9em+74PAuf07YN4xj8e+FLiYbvljH+BXoXvHDfArwIXAPXRX7IPvevnz/t9vJPnCiPNe1J/7M8AdwHeBt86jLmlO8Q9cSFIbvEKXpEbMGehJLuo/CPGlGfqT5MNJNia5JcmLJl+mJGku41yhXwysnqX/BLq1zCOAM4CP7npZkqT5mjPQq+oz7Pj+30EnApdU5zrgoCRPm1SBkqTxTGKDouVs/2GMzX3b14YHJjmD7iqe/fff/8eOPPLICTy8NBkb7nlwxr7nLz9wN1YizezGG2+8v6qWjeqbRKBnRNvIt85U1VpgLcCqVatq/fr1E3h4aTJeet7fcM83d9wRYPlB+/L357xiChVJO0ry1Zn6JvEul81s/+m6FXSfipP2KO88/rnsu9f227bsu9cS3nn8c6dUkTQ/kwj0K4BT+3e7vAR4sKp2WG6RFrvXvnA5H3z989l7Sfdjsfygffng65/Pa1+4fMqVSeOZc8klyceA44BD+v2gf4tuwyKqag2wDngV3SZJ32H0J/qkPcJrX7icj11/FwB/+u9/YsrVSPMzZ6BX1clz9BfwlolVJEnaKX5SVJIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJasRYgZ5kdZLbk2xMcs6I/gOTXJnk5iS3Jjlt8qVKkmYzZ6AnWQJcAJwArAROTrJyaNhbgNuq6mjgOOD3kuw94VolSbMY5wr9WGBjVW2qqkeAy4ATh8YU8MQkAQ4AHgC2TrRSSdKsxgn05cDdA8eb+7ZB5wNHAfcCG4Bfq6rHhk+U5Iwk65Os37Jly06WLEkaZZxAz4i2Gjo+HrgJeDpwDHB+kiftcKeqtVW1qqpWLVu2bJ6lSpJmM06gbwYOHTheQXclPug04PLqbATuAI6cTImSpHGME+g3AEckObx/ofMk4IqhMXcBrwRI8lTgucCmSRYqSZrd0rkGVNXWJGcBVwNLgIuq6tYkZ/b9a4D3Axcn2UC3RHN2Vd2/gHVLkobMGegAVbUOWDfUtmbg9r3Az0y2NEnSfPhJUUlqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNGCvQk6xOcnuSjUnOmWHMcUluSnJrkr+dbJmSpLksnWtAkiXABcC/BjYDNyS5oqpuGxhzEPARYHVV3ZXkhxeoXknSDMa5Qj8W2FhVm6rqEeAy4MShMb8IXF5VdwFU1X2TLVOSNJdxAn05cPfA8ea+bdBzgIOTfDrJjUlOHXWiJGckWZ9k/ZYtW3auYknSSOMEeka01dDxUuDHgFcDxwPvSfKcHe5UtbaqVlXVqmXLls27WEnSzOZcQ6e7Ij904HgFcO+IMfdX1cPAw0k+AxwNfGUiVUqS5jTOFfoNwBFJDk+yN3AScMXQmE8AP5VkaZL9gB8HvjzZUiVJs5nzCr2qtiY5C7gaWAJcVFW3Jjmz719TVV9O8ingFuAx4MKq+tJCFi5J2t44Sy5U1Tpg3VDbmqHjDwEfmlxpkqT58JOiktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSI8YK9CSrk9yeZGOSc2YZ9+Ikjyb5t5MrUZI0jjkDPckS4ALgBGAlcHKSlTOM+x3g6kkXKUma2zhX6McCG6tqU1U9AlwGnDhi3FuB/wHcN8H6JEljGifQlwN3Dxxv7tu+L8ly4HXAmtlOlOSMJOuTrN+yZct8a5UkzWKcQM+Itho6/gPg7Kp6dLYTVdXaqlpVVauWLVs2ZomSpHEsHWPMZuDQgeMVwL1DY1YBlyUBOAR4VZKtVfWXkyhSkjS3cQL9BuCIJIcD9wAnAb84OKCqDt92O8nFwFWGuSTtXnMGelVtTXIW3btXlgAXVdWtSc7s+2ddN5ck7R7jXKFTVeuAdUNtI4O8qt6462VJkubLT4pKUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJasRYgZ5kdZLbk2xMcs6I/lOS3NJ/XZvk6MmXKkmazZyBnmQJcAFwArASODnJyqFhdwAvq6oXAO8H1k66UEnS7Ma5Qj8W2FhVm6rqEeAy4MTBAVV1bVX9Y394HbBismVKkuYyTqAvB+4eON7ct83kzcAnR3UkOSPJ+iTrt2zZMn6VkqQ5jRPoGdFWIwcmL6cL9LNH9VfV2qpaVVWrli1bNn6VkqQ5LR1jzGbg0IHjFcC9w4OSvAC4EDihqr4xmfIkSeMa5wr9BuCIJIcn2Rs4CbhicECSw4DLgV+uqq9MvkxJ0lzmvEKvqq1JzgKuBpYAF1XVrUnO7PvXAO8FngJ8JAnA1qpatXBlS5KGjbPkQlWtA9YNta0ZuH06cPpkS5MkzYefFJWkRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhoxVqAnWZ3k9iQbk5wzoj9JPtz335LkRZMvVZI0mzkDPckS4ALgBGAlcHKSlUPDTgCO6L/OAD464TolSXMY5wr9WGBjVW2qqkeAy4ATh8acCFxSneuAg5I8bcK1SpJmsXSMMcuBuweONwM/PsaY5cDXBgclOYPuCh7goSS3z6vaxx0C3L+T911Ii7UuWLy1Ldq6/uzMxVkXi3S+sK752JW6njFTxziBnhFttRNjqKq1wNoxHnP2gpL1VbVqV88zaYu1Lli8tVnX/FjX/Pyg1TXOkstm4NCB4xXAvTsxRpK0gMYJ9BuAI5IcnmRv4CTgiqExVwCn9u92eQnwYFV9bfhEkqSFM+eSS1VtTXIWcDWwBLioqm5NcmbfvwZYB7wK2Ah8Bzht4UoGJrBss0AWa12weGuzrvmxrvn5gaorVTssdUuS9kB+UlSSGmGgS1IjFlWgJ9knyfVJbk5ya5LfHjHmwCRXDow5baBv1i0KpljXnUk2JLkpyfrdXNfBST7eb8lwfZIfHeib5nzNVteCzNfA+Zck+WKSq0b0zbiNxULN1wTqmuZ8HZnkc0n+Ock7hvqmOV+z1TXN+Tql//93S5Jrkxw90Lfr81VVi+aL7v3sB/S39wI+D7xkaMy7gN/pby8DHgD2pnvB9h+AZ/XHNwMrp11Xf3wncMiU5utDwG/1t48ErulvT3u+Rta1kPM1cP63A38CXDWi71XAJ/v/hpcAn1/o+dqVuhbBfP0w8GLgA8A7BtqnPV8j61oE8/WTwMH97RMm/f21qK7Qq/NQf7hX/zX8qm0BT0wS4AC64NzKeFsUTKOuBTNmXSuBa/rx/wd4ZpKnMv35mqmuBZVkBfBq4MIZhsy0jcWCzdcu1rWg5qqrqu6rqhuA7w11TXW+ZqlrQY1R17VV9Y/94XV0n9mBCc3Xogp0+P7TlZuA+4D/VVWfHxpyPnAU3QeXNgC/VlWPMfP2A9OuC7ow+6skN6bb/mBixqjrZuD1/dhj6T42vILpz9dMdcECzhfwB8BvAo/N0D/TvCzofO1CXTDd+ZrJtOdrNotlvt5M96wLJjRfiy7Qq+rRqjqG7of72MG11d7xwE3A04FjgPOTPIkxtx+YQl0AL62qF9E9xXpLkn+1G+s6Dzi4D9e3Al+ke+Yw7fmaqS5YoPlK8hrgvqq6cbZhI9pqlvZp1wXTna8Z7z6ibXfO12ymPl9JXk4X6GdvaxoxbN7ztegCfZuq+ibwaWD1UNdpwOX9U8+NwB10a7C7ZfuBnaiLqrq3//c+4ON0T692S11V9a2qOq0P11Pp1vfvYMrzNUtdCzlfLwV+LsmddE9pX5Hkj4fGzDQvCzlfu1LXtOdrJtOerxlNe76SvIBuSebEqvpG3zyZ+ZrvovtCftH9UB/U394X+CzwmqExHwXe199+KnAP3c5lS4FNwOE8/qLC8xZBXfsDT+zb9weuBVbvxroO4vEXZ/8d3Tosi2C+ZqprweZr6PGPY/SLVq9m+xcfr1/o+drFuqY6XwP972P7F0WnOl+z1DXt76/D6D5R/5ND7ROZr3F2W9ydngb8Ubo/qvEE4M+q6qpsv83A+4GLk2yg++Y+u6ruB8iILQqmXVeSZwEf714rZSnwJ1X1qd1Y11HAJUkeBW6je5pHzbClw7TrovtluFDzNVLG2MZigedrp+tiyvOV5F8A64EnAY8l+XW6d2d8a5rzNVNddBdZ0/z+ei/wFOAjfQ1bq2rVpL6//Oi/JDVi0a6hS5Lmx0CXpEYY6JLUCANdkhphoEtSIwx07ZGSrEjyiST/N8k/JPmv6f5E4mz3edfuqk+aBgNde5x+A7TLgb+sqiOA59BtiPaBOe5qoKtpBrr2RK8AvltV/w26fWOAtwFvSvIrSc7fNjDJVUmOS3IesG+/B/Z/7/tO7felvjnJpX3bM5Jc07dfk+Swvv3iJB9N8r+TbErysiQXJflykosHHu9n0u3D/YUkf57kgL79vCS39ef9L7tpnvQDZrF9UlQax/OA7TZA6j+ZeBczfE9X1TlJzqpu7xiSPA94N91GTfcneXI/9Hy6bQj+KMmbgA8Dr+37Dqb7ZfJzwJV0e3ecDtyQ5Bi6/TjOBX66qh5Ocjbw9v4XzOuAI6uqkhw0gTmQdmCga08URu9EN1P7KK8A/mLbthFV9UDf/hP02/oClwK/O3CfK/tA3gB8vao2ACS5FXgm3YZKK4G/7z/WvTfwOeBbwHeBC5P8T2CHv2QjTYKBrj3RrcC/GWzotyo+FHiQ7ZcS95nhHOOG/+CYf+7/fWzg9rbjpcCjdHu/n7zDg3V7vr8SOAk4i+4XijRRrqFrT3QNsF+SU6H7YxrA7wEX0+1Yd0ySJyQ5lO23Rv1ekr0GzvHzSZ7Sn2Pbksu1dKELcArwd/Oo6zrgpUme3Z9zvyTP6dfRD6yqdcCv0+2XL02cV+ja4/TLHq+j27HuPXQXJuvo3sXyCN2+6huALwFfGLjrWuCWJF+oqlOSfAD4237Hxy8CbwR+FbgoyTuBLTy+q+E4dW1J8kbgY0l+qG8+F/g28Ikk+9A9M3jbzv2XS7Nzt0VJaoRLLpLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNeL/A5VvBtf/d5u5AAAAAElFTkSuQmCC\n", "text/plain": "
" }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ] } }, "c0d691038d5d43339a572283a2673697": { "model_module": "@jupyter-widgets/controls", "model_module_version": "1.5.0", "model_name": "SliderStyleModel", "state": { "_model_module": "@jupyter-widgets/controls", "_model_module_version": "1.5.0", "_model_name": "SliderStyleModel", "_view_count": null, "_view_module": "@jupyter-widgets/base", "_view_module_version": "1.2.0", "_view_name": "StyleView", "description_width": "", "handle_color": null } }, "c24a3456f53e453d86b6cf16a1b93f6e": { "model_module": "@jupyter-widgets/controls", "model_module_version": "1.5.0", "model_name": "VBoxModel", "state": { "_dom_classes": [ "widget-interact" ], "_model_module": "@jupyter-widgets/controls", "_model_module_version": "1.5.0", "_model_name": "VBoxModel", "_view_count": null, "_view_module": "@jupyter-widgets/controls", "_view_module_version": "1.5.0", "_view_name": "VBoxView", "box_style": "", "children": [ "IPY_MODEL_c90aaa6d9d2843f8b426ad65a5442410", "IPY_MODEL_a6ba747e0c9c4628aa3cf885881d4e57" ], "layout": "IPY_MODEL_42dfa5cef9dd4789989839863ebc0b32" } }, "c90aaa6d9d2843f8b426ad65a5442410": { "model_module": "@jupyter-widgets/controls", "model_module_version": "1.5.0", "model_name": "IntSliderModel", "state": { "_dom_classes": [], "_model_module": "@jupyter-widgets/controls", "_model_module_version": "1.5.0", "_model_name": "IntSliderModel", "_view_count": null, "_view_module": "@jupyter-widgets/controls", "_view_module_version": "1.5.0", "_view_name": "IntSliderView", "continuous_update": false, "description": "n:", "description_tooltip": null, "disabled": false, "layout": "IPY_MODEL_16d235d5152e45d49928294e6418e24c", "max": 200, "min": 1, "orientation": "horizontal", "readout": true, "readout_format": "d", "step": 1, "style": "IPY_MODEL_c0d691038d5d43339a572283a2673697", "value": 1 } }, "e5ec282970c141eea017482cb19e10fd": { "model_module": "@jupyter-widgets/base", "model_module_version": "1.2.0", "model_name": "LayoutModel", "state": { "_model_module": "@jupyter-widgets/base", "_model_module_version": "1.2.0", "_model_name": "LayoutModel", "_view_count": null, "_view_module": "@jupyter-widgets/base", "_view_module_version": "1.2.0", "_view_name": "LayoutView", "align_content": null, "align_items": null, "align_self": null, "border": null, "bottom": null, "display": null, "flex": null, "flex_flow": null, "grid_area": null, "grid_auto_columns": null, "grid_auto_flow": null, "grid_auto_rows": null, "grid_column": null, "grid_gap": null, "grid_row": null, "grid_template_areas": null, "grid_template_columns": null, "grid_template_rows": null, "height": null, "justify_content": null, "justify_items": null, "left": null, "margin": null, "max_height": null, "max_width": null, "min_height": null, "min_width": null, "object_fit": null, "object_position": null, "order": null, "overflow": null, "overflow_x": null, "overflow_y": null, "padding": null, "right": null, "top": null, "visibility": null, "width": null } } }, "version_major": 2, "version_minor": 0 } } }, "nbformat": 4, "nbformat_minor": 5 }